package Top_Interview_Questions.Dynamic_Programming;

import java.util.Arrays;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/4 11:21
 * <p>
 * https://leetcode-cn.com/problems/unique-paths/solution/dong-tai-gui-hua-by-powcai-2/
 */
public class _0062 {

    public static void main(String[] args) {
        _0062 test = new _0062();
        test.uniquePaths1(3,4);

    }

    /**
     * 优化之后的动态规划,
     * 当前的状态只跟上一行的状态和同一行左边的状态有关。所以我们只需要维护上一行的数组，和当前行的数组
     */
    public int uniquePaths1(int m, int n) {
        int[] cur = new int[n];
        Arrays.fill(cur,1);
        for (int i = 1; i < m;i++){
            for (int j = 1; j < n; j++){
                cur[j] += cur[j-1] ;
            }
        }
        return cur[n-1];
    }



    /**
     * 动态规划
     * dp[i][j] 是到达 i, j 最多路径
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }


}
